import java.util.*;

class WordsFrequency {
    Map<String ,Integer> map=new HashMap<>();
    public WordsFrequency(String[] book) {
        for(String str:book){
            map.put(str,map.getOrDefault(str,0)+1);
        }
    }

    public int get(String word) {
        return map.getOrDefault(word,0);
    }
}
public class project {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for(String str : strs){
            char[] arr=str.toCharArray();
            Arrays.sort(arr);
            String tmp=new String(arr);
            List<String> list=map.getOrDefault(tmp,new ArrayList<>());
            list.add(str);
            map.put(str,list);
        }
        return new ArrayList<>(map.values());
    }









    public List<Integer> partitionLabels(String s) {
        List<Integer> list=new ArrayList<>();
        int left=0;
        int right=0;
        int len=s.length();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<len;i++){
            map.put(s.charAt(i),i);
        }
        int cur=0;
        while(right<len){
            while (cur<=right){
                right=Math.max(right,map.get(s.charAt(cur)));
                cur++;
            }
            list.add(right-left+1);
            left=right++;
        }
        return list;
    }
















    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> list=new ArrayList<>();
        Map<Integer,List<Integer>> map=new HashMap<>();
        for(int i=0;i<groupSizes.length;i++){
            int tmp=groupSizes[i];
            if(!map.containsKey(tmp)){
                map.put(tmp,new ArrayList<>());
            }
            List<Integer> arr=map.get(tmp);
            arr.add(i);
            map.put(tmp,arr);
            if(arr.size()==tmp){
                list.add(new ArrayList<>(arr));
                arr.clear();
            }
        }
        return list;
    }















    public String originalDigits(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        int[] arr=new int[10];
        arr[0]=map.getOrDefault('z',0);
        arr[2]=map.getOrDefault('w',0);
        arr[4]=map.getOrDefault('u',0);
        arr[6]=map.getOrDefault('x',0);
        arr[8]=map.getOrDefault('g',0);
        arr[3]=map.getOrDefault('h',0)-arr[8];
        arr[5]=map.getOrDefault('f',0)-arr[4];
        arr[7]=map.getOrDefault('s',0)-arr[6];
        arr[1]=map.getOrDefault('o',0)-arr[0]-arr[2]-arr[4];
        arr[9]=map.getOrDefault('i',0)-arr[5]-arr[6]-arr[8];
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<10;i++){
            for(int j=0;j<arr[i];j++){
                sb.append((char)i+'0');
            }
        }
        return sb.toString();
    }
}
